/*
 * 最接近的三数之和
 * https://leetcode-cn.com/problems/3sum-closest/
 */
int cmp(void *a, void *b) {return *(int *)a - *(int *)b;}
int threeSumClosest(int* nums, int numsSize, int target){
    if (numsSize == 3) return nums[0] + nums[1] + nums[2];
    int best = 1e7;
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i < numsSize; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int j = i + 1;
        int k = numsSize - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target) return target;
            if (abs(sum - target) < abs(best - target)) {
                best = sum;
            }
            (sum > target) ? k-- : j++;
        }
    }
    return best;
}